Національний університет “КИЄВО-МОГИЛЯНСЬКА АКАДЕМІЯ” департамент комп’ютерних технологій кафедра інформатики Реалізація ідеї арифметичного кодування. Курсова робота студента четвертого курсу Кравченка Івана Науковий керівник к. фіз-мат. н. доц. Ставровський А.Б. Київ - 1999 Зміст. 1. Вступ. 2. Ідея арифметичного кодування. 3. Програма для арифметичного кодування. 3.1 Алгоритм арифметичного кодування. 3.2 Алгоритм арифметичного декодування. 4. Зауваження до реалізації. 4.1 Прирощувані передача і отримання інформації. 4.2 Бажане використання цілочисленої арифметики. 4.3 Ефективна реалізація моделі. 5. Реалізація моделі. 6. Доведення правильності декодування. 7. Проблема переповнення і завершення кодування. 7.1 Від’ємне переповнення. 7.2 Переповнення. 7.3 Завершення кодування. 8. Моделі для арифметичного кодування. 8.1 Фіксовані моделі. 8.2 Адаптивна модель. 9. Ефективність стискання. 10. Застосування арифметичного кодування. 10.1 Кодування чорно – білих зображень. 10.2 Кодування довільно розподілених цілих чисел. Додаток 1. Доведення декодуючої нерівності. Додаток 2. Робочий код для адаптивного арифметичного стискання. Література. Вступ. Проблема стискання та кодування інформації з’явилась набагато раніше ніж, власне, термін “інформація”. Згадаємо, що принаймні за часів Римсокої імперії армія використовувала метод шифрування повідомлень з метою її захисту від ворогів. Так званий шифр Цезаря став першим з відомих на сьогодні методів шифрування з таємним ключом. Іншим прикладом кодування є писемність, яка виникла так давно, що точних даних про конкретний час її появи не існує і, мабуть, ніколи не буде знайдено. В другій половині ХХ-го століття з винайденням та розвитком ЕОМ проблема стискання та кодування привернула до себе увагу, бо з чисто теоретичної перетворилася в прикладну та вкрай необхідну. Стрімко зросли обсяги даних, з’явилась потреба в передачі дискретної інформації на далекі відстані з достатньою надійністю, проблема захисту такої інформації від несанкціанованого доступу і т. д. З розвитком комп’ютерних мереж (зокрема, INTERNET) обсяг інформації, що передається, швидко зростає і вимагає її мінімізації шляхом специфічного кодування для підтримання швидкодії мережі. Можна навести багато інших застосувань кодування інформації. Арифметичне кодування є одним з перспективних методів стиску інформації, та, в деякому розумінні, її шифрування. Це кодування дозволяє пакувати символи вхідного алфавіту за умови, що розподіл частот цих символів відомий. Концепція методу була розроблена Еліасом в 60-х роках. Після цього метод був суттєво розвинутий та вдосконалений. Арифметичне кодування є оптимальним, досягає теоретичної границі ступеня стиску, - ентропії вхідного потоку. 2. Ідея арифметичного кодування. При арифметичному кодуванні текст представляється числами з плаваючою комою в інтервалі від 0 до 1. В процесі кодування тексту інтервал, що його відображає – зменшується, а кількість бітів для його представлення збільшується. Наступні символи тексту зменшують величину інтервала, виходячи з значень їх ймовірностей, які визначаються моделлю. Більш ймовірні символи роблять це в меншій мірі ніж менш ймовірні та, таким чином, додають менше бітів до результату. Перед початком роботи відповідний до тексту інтервал є [0 ; 1). При обробці наступного символу його ширина звужується за рахунок виділення цьому символу частини інтервалу. Наприклад, застосуемо до тексту “еаіі!” алфавіта {а, е, і, о, u, ! } модель з постійними ймовірностями, що задані в таблиці 1. Таблиця 1. Приклад постійної моделі для алфавіта {а, е, і, о, u, ! }. Символ Ймовірність Інтервал  А 0,2 [0,0; 0,2)  Е 0,3 [0,2; 0,5)  І 0,1 [0,5; 0,6)  О 0,2 [0,6; 0,8)  У 0,1 [0,8; 0,9)  ! 0,1 [0,9; 1,0)   І кодувальнику, і декодувальнику відомо, що на самому початку інтервал є [0; 1). Після перегляду першого символу “е”, кодувальник звужує інтервал до [0,2; 0,5), який модель виділяє цьомк символу. Другий символ “а” звузить цей новий і...